package BinaryTree.review;

import 其他.DataStructure.TreeNode;
import MyUtils.MHUtils;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

public class 反序列化 {
    @Test
    public void test(){
        TreeNode root = strTotree("1,2,3,5,null,null,4");
        String s = MHUtils.treeToStr(root);
        System.out.println(s);
    }

    /*

    n不存que 无后续处理
    que暂存递归栈 的 之前引用地址 直接拿

    que层序递归栈tmp

    stack 前中后递归栈
    练

     */
    public TreeNode strTotree(String s){
        String[] strs = s.split(",");
        Queue<String> q1 = new LinkedList<>();
        for (String str : strs) {
            q1.add(str);
        }
        Queue<TreeNode> q2 = new LinkedList<>();

        int f=0;
        TreeNode resRot = null;

        String c = q1.poll();
        //后补
        q2.add(new TreeNode(Integer.parseInt(c)));

        while(!c.equals("over")){
//            TreeNode cNode = new TreeNode(Integer.parseInt(c));
            TreeNode cNode = q2.poll();
            if(f==0){
                resRot = cNode;
                f++;
            }
            // null也要弹出来poll / 但是不能后面又poll
//            TreeNode leftT = q1.poll().equals("null")?null:new TreeNode(Integer.parseInt(q1.poll()));
//            cNode.left = leftT;
//            TreeNode rightT = q1.poll().equals("null")?null:new TreeNode(Integer.parseInt(q1.poll()));
//            cNode.right = rightT;
            String pollStr = q1.poll();
            TreeNode leftT = null;
            TreeNode rightT = null;
            if(pollStr.equals("null")){
                cNode.left=null;
            }
            else {
                leftT = new TreeNode(Integer.parseInt(pollStr));
                cNode.left = leftT;
            }

            pollStr = q1.poll();
            if(pollStr.equals("null")){
                cNode.right=null;
            }else {
                rightT = new TreeNode(Integer.parseInt(pollStr));
                cNode.right = rightT;
            }

            if(leftT!=null){
                q2.add(leftT);
            }
            if(rightT!=null){
                q2.add(rightT);
            }

            //W迭代
            if(q1.isEmpty()){
//            if(q2.isEmpty()){
                c = "over";
                continue;
            }
//            c = q2.poll().val+"";
        }
        return resRot;
    }
}
